package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author yinlei
 * @date 2018/6/21
 * @since 1.0.0
 */
public class N033SearchInRotatedSortedArray {

    public static void main(String[] args) {

        List list = new ArrayList(5000);
        for (int i = 0; i < 5000; i++) {
            list.add(i);
        }

        System.out.println(list);
//
//        int[] arr = new int[]{4,5,6,7,0,1,2};
//        for (int a : arr) {
//            System.out.println(search(new int[]{4,5,6,7,0,1,2}, a));
//        }
//        System.out.println(search(new int[]{4,5,6,7,0,1,2}, 3));
//        System.out.println(search(new int[]{5,1,3}, 3));
//        System.out.println(search(new int[]{5,1,3}, 5));
//        arr = new int[]{4,5,6,7,8,1,2,3};
//        for (int a : arr) {
//            System.out.println(search(arr, a));
//        }
//        System.out.println(search(arr, 8));
    }

    static public int search(int[] nums, int target) {

        int length = nums.length;

        return search(nums, target, 0, length - 1);
    }

    private static int search(int[] nums, int target, int start, int end) {
        if (start > end) return -1;

        int mid = (start + end) / 2;
        int midNum = nums[mid];
        if (midNum == target) {
            return mid;
        }
        if (midNum < target) {
            if (midNum > nums[end]) {
                start = mid + 1;
            } else if (nums[start] > midNum) {
                end = mid - 1;
            } else {
                return -1;
            }
        } else { // mid > target
            if (midNum > nums[end]) {
                start = mid + 1;
            } else if (midNum < nums[start]) {
                end = mid - 1;
            } else {
                return -1;
            }
        }

        return -1;
    }
}

